package com.algorithm.lesson_04;

import java.util.Stack;

/**
 * 用辅助栈实现，辅助栈保存当前栈最小元素
 * 
 * @author Administrator
 *
 */
public class GetMinStackImpl1 implements GetMinStack<Integer> {

	private Stack<Integer> dataStack; // 数据栈
	private Stack<Integer> minStack; // 辅助栈，保存最小值

	public GetMinStackImpl1() {
		dataStack = new Stack<>();
		minStack = new Stack<>();
	}

	@Override
	public boolean isEmpty() {
		return dataStack.isEmpty();
	}

	@Override
	public Integer peek() {
		if (dataStack.isEmpty()) {
			throw new RuntimeException("Your Stack is Empty!");
		}
		return dataStack.peek();
	}

	@Override
	public Integer pop() {
		if (dataStack.isEmpty()) {
			throw new RuntimeException("Your Stack is Empty!");
		}
		// 出栈操作
		// 数据栈和最小值栈一同出栈
		minStack.pop();
		return dataStack.pop();
	}

	@Override
	public void push(Integer t) {
		// 压栈操作
		if (dataStack.isEmpty()) {
			// 栈为空，直接将数据压入数据栈和最小值栈
			dataStack.push(t);
			minStack.push(t);
			return;
		}
		Integer top = minStack.peek();
		// t<top? push-->t else push--> top
		Integer push = t < top ? t : top;
		dataStack.push(t);
		minStack.push(push);
	}

	@Override
	public Integer getMin() {
		if(minStack.isEmpty()) {
			throw new RuntimeException("Your Stack is Empty!");
		}
		return minStack.peek();
	}

}
